The present invention relates to a neural net model used as a method and a system for solving optimization problems, recognition problems, etc. under some constraints. The present invention also relates to a neural net optimizing method and system for realizing the neural net model.
As a neural net for solving optimization problems under some constraints, the Hopfield model is known. In this model, neurons are connected to each other by synapses each having a fixed synaptic weight W, and the respective states of the neurons are sequentially (asynchronously) updated one by one. Therefore, this model has the problem that the processing is not efficient. Accordingly, it has been expected to carry out the processing in parallel and efficiently by performing synchronous state updating.
In the meantime, as a neural net model for synchronous processing, a recursive neural net has been devised, which performs block-sequential state updating in which synchronous and asynchronous operations are jointly used (see Recursive Neural Networks for Associative Memory, pp. 33-35, Wiley). The block-sequential state updating is a processing method in which a network comprising n neurons is divided into m blocks, and while synchronous state updating is being performed within each individual block, state updating is sequentially (asynchronously) performed from the first block to the m-th block. However, this model is a binary model and therefore limited in the application range.
The recursive neural net model will be explained below. FIG. 1 shows the input/output function in a conventional binary neural net that performs block-sequential state updating.
In the recursive neural net model, the state vector x=(x.sub.1, . . . , x.sub.n).sup.T, where x.sub.i =0 or 1, is divided into m subvectors x.sup.(k) (k=1, . . . , m) , and each subvector is updated according to the following expression: ##EQU1##
In the above expression (1), .THETA..sup.(k) represents subvectors of the threshold vector .THETA.=[.THETA..sup.(1)T, .THETA..sup.(2)T, . . . , .THETA..sup.(m)T ].sup.T, and W.sub.kj is a submatrix of synaptic weights of the link connecting the j-th block to the k-th block, which is related to the synaptic matrix W by the following expression: ##EQU2##
The Sgn function causes the sgn function defined below to operate for each vector component (the input/output function thereof is shown in FIG. 1): ##EQU3##
With respect to the synaptic matrix W, which is a symmetric matrix, an energy function is defined by: ##EQU4##
With regard to the energy function, the following has been proved. That is, assuming that the diagonal blocks W.sub.kk in the synaptic matrix W are positive definite, i.e., if the following condition is assumed to hold for any subvector x.sup.(k) : EQU x.sup.(k)T W.sub.kk x.sup.(k) .gtoreq.0 (5)
(the equality sign holds only when x.sup.(k) =0) then, for the energy function, the following condition holds: EQU E(t+1).ltoreq.E(t) (6)
(the equality sign holds only when X(t+1)=X(t))
In other words, the energy inevitably decreases with the passage of time. Accordingly, if the given optimization problem is to minimize the evaluation function in the form of the expression (4), it can be solved by applying the above-described neural net as long as the diagonal blocks W.sub.kk in the synaptic matrix W are positive definite.
Further, a method of solving optimization problems, recognition problems, etc. by optically performing vector matrix calculation and realizing a neural net has heretofore been known (for example, see The Journal of Applied Optics, Vol. 24, No. 10, pp. 1469-1475, 1985). FIG. 2 is a basic conceptual view showing one example of the arrangement of the conventional neural net, in which an associative memory system is realized by an optical method based on the Hopfield model. In this optical computer system, reference numeral 101 denotes an light-emitting element array, 102 and 104 lenses, 103 an optical mask, e.g., a photographic mask, 105 a photosensor array, 106 a threshold processing unit, and 107 a nonlinear computing unit.
The operation of the above system will be explained below. A sectorial beam of light is applied to the optical mask 103 from the light-emitting element array 101. The light-emitting element array 101 represents a kind of vector x=(x.sub.1, x.sub.2, . . . , x.sub.n) in which the state is expressed by the intensity of light emitted from each element. The optical mask 103 is divided into n.times.n elements. The light transmittance of each element represents a kind of matrix W=[w.sub.ij ] which expresses the synaptic weight of the link connecting neurons to each other. The photosensor array 105 represents a kind of vector u=u(u.sub.1, u.sub.2, . . . , u.sub.n). The j-th light-emitting element illuminates the j-th row of the optical mask 103 through the lens system 102, and the sum of light intensities in the i-th column of the optical mask 103 is received by the i-th photosensor through the lens system 104. In this way, it is possible to perform the following vector matrix calculation: ##EQU5##
Next, the signal obtained by the photosensor is input to the threshold processing unit 106 where it is subjected to the following threshold processing: EQU S.sub.i =u.sub.i +.theta..sub.i ( 8)
Further, the value S.sub.i is subjected to nonlinear processing in the nonlinear computing unit 107 as follows: ##EQU6##
Then, the resulting signal is fed back to the light-emitting element array 101. Thus, it is possible to realize a Hopfield neural net and find an optimal solution.
However, the above-described binary model that performs block-sequential state updating is limited in the application range because of the imposed condition that the diagonal blocks W.sub.kk in the synaptic matrix W must be positive definite. Therefore, it is difficult to apply it to various optimization problems.
In addition, the above-described system, in which a Hopfield neural net is realized by using light, can perform high-speed processing because the vector matrix calculation, which requires the processing time the most, is executed by light. Further, the system needs no complicated wiring, which would be a fatal disadvantage in the case of electrical systems. Thus, the system is excellent. However, it is generally known that since the system performs discrete-time synchronous updating, there are many cases where an oscillating solution occurs and no optimal solution can be obtained. In actual fact, there are many oscillating solutions in the results shown in the aforementioned literature. Thus, there is much room for further improvement.